//
//  XBSortBinTree.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/24.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBSortBinTree.h"
#include<stdio.h>
typedef struct node
{
    int data;
    struct node *l;
    struct node *r;
} Node;
// -- 删除的是没写。。

Node* search(Node *t,int x)
{
    Node *p;
    p=t;
    if(p==NULL)
    {
        return NULL;
    }
    else
    {
        if(p->data==x)
        {
            return t;
        }
        else if(x>p->data)
        {
            search(p->l,x);
        }
        else
        {
            search(p->r,x);
        }
    }
    return p;
}

Node* search_2(Node *t,int x)
{
    Node *p;
    p=t;
    while(!p)
    {
        if(x==p->data)
        {
            return p;
        }
        else if(x>p->data)
        {
            p=p->r;
        }
        else
        {
            p=p->l;
        }
    }
    return p;
}
void insert(Node **t,Node *s)//t是二叉树根结点指针的地址
{
    if(*t==NULL)//插入头部
    {
        *t=s;
    }
    else
    {
        if(s->data<(*t)->data)
        {
            insert(&((*t)->l),s);
        }
        else  if(s->data>(*t)->data)
        {
            insert(&((*t)->r),s);
        }
        else
        {
            printf("已经在里面了!\n");
        }
    }
}

void creatSortT(Node **t)//创建有序二叉树
{
    int x;
    Node *s;
    printf("输入数据，-1结束.\n");
    scanf("%d",&x);
    while(x!=-1)
    {
        s=(Node *)malloc(sizeof(Node));
        s->data=x;
        s->l=NULL;
        s->r=NULL;
        insert(t,s);
        scanf("%d",&x);
    }
}
void mid_visit(Node*t)
{
    if(t==NULL)
        return;
    else
    {
        mid_visit(t->l);
        printf("%d,",t->data);
        mid_visit(t->r);
    }
    
}

void testSortBinT()
{
    Node *root=NULL;
    printf("\n创建一棵二叉排序树");
    creatSortT(&root);
    printf("二叉排序树的序列是:\n");
    mid_visit(root);
    
}  
